from tkinter import *#导入tkinter库
from tkinter import messagebox
import tkinter as tk
class basedesk():#底板
    def __init__(self, master):
        self.master = master
        self.master.title("二叉树模拟器")#标题
        self.master.configure(bg='#B1FFF9')#设置背景颜色
        self.master.geometry("1000x600")#设置窗口尺寸
        mainwindow(self.master)#生成主界面
class mainwindow():#标题页面
    def __init__(self, master):
        self.master = master
        self.window = tk.Frame(self.master, bg='#FFFFFF')#生成一个框架来展示标题页面
        self.window.place(x=0,y=0,width=1000,height=600)#设置框架的位置
        self.window.showname_label=tk.Label(self.window,text="二叉树模拟器",fg='#FFFFFF', bg='#CEB434',font=("Helvetic",100,"bold"),relief=RAISED)#生成一个标题label
        self.window.showname_label.place(x=0, y=10,width=1000, height=150)#设置标题的位置
        self.window.showinfo_label = tk.Label(self.window,text="前序遍历：先访问根节点，\n接着遍历左节点，最后遍历右节点\n中序遍历：先遍历左节点，\n接着访问根节点，最后遍历右节点\n后序遍历：先遍历左节点，\n接着遍历右节点，最后访问根节点",fg='#615A36',bg='#FFF2AE',font=("Helvetic",25,"bold"))#生成一个说明label
        self.window.showinfo_label.place(x=20,y=200)#设置说明label的位置
        self.window.enter_btn=tk.Button(self.window,text="开始",bg='#000000',fg='#FFFFFF',font=("Helvetic", 60, "bold"),command=self.changetofunction)#生成一个开始按钮
        self.window.enter_btn.place(x=700, y=200,width=250, height=150)#设置开始按钮的位置
        self.window.close_btn=tk.Button(self.window,text="关闭",bg='#000000',fg='#FFFFFF',font=("Helvetic", 60, "bold"),command=self.close)#生成一个关闭按钮
        self.window.close_btn.place(x=700, y=400,width=250, height=150)#设置关闭按钮的位置
    def changetofunction(self):#切换到功能页面
        self.window.destroy()#摧毁框架
        functionwindow(self.master)#生成功能页面
    def close(self):#关闭软件
        self.master.destroy()#关闭主循环
class functionwindow():#功能页面
    def __init__(self, master):#功能页面构造函数
        self.master = master
        self.start_lock=0#判断是否为第一个节点
        self.point_num=1#用于计算节点号
        self.draw_father=[]#绘制父节点
        self.window = tk.Frame(self.master, bg='#B1EBC2')#生成一个框架作为功能页面
        self.window.place(x=0,y=0,width=1000,height=600)#放置功能页面框架
        self.window.show_listbox = tk.Listbox(self.window,font=("Helvetica",20))#生成一个listbox用于提示当前的步骤
        self.window.show_listbox.place(x=10, y=10, width=270, height=34)#放置用于选择插入节点位置的listbox
        self.window.show_listbox.insert(END, '请插入第1个节点')#在选择插入节点位置的listbox后面插入提示
        self.window.showplace_label = tk.Label(self.window,text="选择插入的位置",fg='#000000',bg='#B1EBC2',font=("Helvetic",20,"bold"),relief=RAISED).place(x=10, y=48,width=270, height=30)#提示选择插入的位置的label
        self.window2 = tk.Frame(self.window, bg='#FFD966')#生成一个框架用于部署选择节点listbox
        self.window2.place(x=10, y=80, width=266, height=350)#放置选择节点框架
        self.window2.select_node_scrollbar = tk.Scrollbar(self.window2)#生成一个用于选择节点listbox的滚动轴
        self.window2.select_node_scrollbar.pack(side=RIGHT, fill=Y)#放置选择节点listbox滚动轴
        self.window2.select_node_listbox = tk.Listbox(self.window2,font=("Helvetic",15,"bold"), yscrollcommand=self.window2.select_node_scrollbar.set)#生成一个选择节点listbox
        self.window2.select_node_listbox.place(x=0, y=0, width=250, height=350)#放置选择节点listbox
        self.window2.select_node_listbox.insert(END, '[第一个节点不指定位置]')#在选择节点listbox末尾插入内容
        self.window.insert_btn=tk.Button(self.window,text="插入该节点",bg='#A5BF2F',fg='#FFFFFF',font=("Helvetic", 20, "bold"),command=self.insert_point)#生成一个用于插入节点的按钮
        self.window.insert_btn.place(x=10,y=436,width=270, height=50)#放置插入节点的按钮
        self.window.calculate_btn=tk.Button(self.window,text="计算三序",bg='#1CBF4A',fg='#FFFFFF',font=("Helvetic", 20, "bold"),command=self.calculate)#生成一个计算三序的按钮
        self.window.calculate_btn.place(x=10,y=491,width=270, height=50)#放置计算三序的按钮
        self.window.replace_btn=tk.Button(self.window,text="重置",bg='#9ED2FF',fg='#000000',font=("Helvetic", 20, "bold"),command=self.cleanall)#生成一个重置按钮
        self.window.replace_btn.place(x=10,y=546,width=270, height=50)#放置重置按钮
        self.window.showtree_label = tk.Label(self.window,text="红色箭头代表左子树，蓝色箭头代表右子树，点击节点可查看详细信息",fg='#000000',bg='#B1EBC2',font=("Helvetic",15,"bold"),relief=RAISED)#生成一个label用于说明右边的展示图
        self.window.showtree_label.place(x=290, y=10,width=700, height=30)#放置用于说明右边的展示图的label
        self.tree_canvas = tk.Canvas(self.window,bg='#EAF4C0',relief=SUNKEN)#生成一个画布用于展示二叉树
        self.tree_canvas.place(x=290,y=50, width=700, height=540)#放置二叉树画布
        self.build_tree()#构建二叉树后端数据
        self.the_world=[[[350,50]],[[175, 150],[525, 150]],[[87.5, 250],[262.5, 250],[437.5, 250],[612.5, 250]],[[43.75, 350],[131.75, 350],[218.75, 350],[306.25, 350],[393.75, 350],[481.25, 350],[568.75, 350],[656.25, 350]],[[21.75, 450],[65.75, 450],[109.75, 450],[153.75, 450],[196.75, 450],[240.75, 450],[284.25, 450],[328.25, 450],[371.75, 450],[415.75, 450],[459.25, 450],[503.25, 450],[546.75, 450],[590.75, 450],[634.25, 450],[678.25, 450]]]#定义每个待插入二叉树节点的位置坐标
    def refresh_times(self):#更新用于提示步骤的listbox内的内容
        self.window.show_listbox.delete(0, END)#删除用于提示步骤的listbox内的内容
        self.window.show_listbox.insert(END,'请插入第'+str(self.point_num)+'个节点')#插入用于提示步骤的listbox内的内容
    def cleanall(self):#重置所有数据
        self.check_yes_message = messagebox.askokcancel("确认提醒", "确定要重置所有数据么？")#用一个提示框确定是否要重置所有数据
        if self.check_yes_message == False:#如果选择取消，则放弃重置
            return
        else:#重置数据的原理是重新进入页面
            messagebox.showinfo("提醒", "数据已清空")
            self.window.destroy()
            functionwindow(self.master)
    def calculate(self):#计算三序
        if self.start_lock==0:#判断是否已经插入节点
            messagebox.showerror('错误','请至少插入一个节点')
            return
        forward=self.forward_seq()#前序计算
        middle=self.middle_seq()#中序计算
        backward=self.backward_seq()#后序计算
        forward_text='前序：'
        middle_text = '中序：'
        backward_text = '后序：'
        for i in range(len(forward)):
            forward_text+='['+str(forward[i])+']'
            middle_text += '[' + str(middle[i]) + ']'
            backward_text += '[' + str(backward[i]) + ']'
        messagebox.showinfo('输出结果',forward_text+'\n'+middle_text+'\n'+backward_text+'\n')
    def forward_seq(self):#计算前序
        agent=[]
        for i in range(len(self.main_tree)):
            for j in range(len(self.main_tree[i])):
                if i == 0:
                    agent.append(self.main_tree[i][j])
                    break
                if self.main_tree[i][j] != 0:
                    m, n = self.child_to_root(i, j)
                    detect = agent.index(self.main_tree[m][n])
                    if j%2==0:
                        agent.insert(detect+1,self.main_tree[i][j])
                    else:
                        if self.main_tree[i][j-1]==0:
                            agent.insert(detect + 1, self.main_tree[i][j])
                        else:
                            agent.insert(detect + 2, self.main_tree[i][j])
        return agent
    def middle_seq(self):#计算中序
        agent=[]
        for i in range(len(self.main_tree)):
            for j in range(len(self.main_tree[i])):
                if i == 0:
                    agent.append(self.main_tree[i][j])
                    break
                if self.main_tree[i][j] != 0:
                    m, n = self.child_to_root(i, j)
                    detect = agent.index(self.main_tree[m][n])
                    if j%2==0:
                        agent.insert(detect,self.main_tree[i][j])
                    else:

                        agent.insert(detect + 1, self.main_tree[i][j])

        return agent
    def backward_seq(self):#计算后序
        agent=[]
        for i in range(len(self.main_tree)):
            for j in range(len(self.main_tree[i])):
                if i == 0:
                    agent.append(self.main_tree[i][j])
                    break
                if self.main_tree[i][j] != 0:
                    m, n = self.child_to_root(i, j)
                    detect = agent.index(self.main_tree[m][n])
                    if j%2!=0:
                        agent.insert(detect,self.main_tree[i][j])
                    else:
                        agent.insert(detect, self.main_tree[i][j])

        return agent
    def insert_point(self):#插入节点
        if self.start_lock!=0:#判断是否为第一个节点
            self.choose_index = self.window2.select_node_listbox.curselection()#获取要插入节点的位置
            if (len(self.choose_index) == 0):
                messagebox.showerror('错误','请选择要插入的位置')
                return
            self.choose_index = list(self.window2.select_node_listbox.curselection())#解析数据
            self.choose_index = self.choose_index[0]
        else:
            self.choose_index =-1
            self.start_lock=1
        if self.choose_index == -1:
            self.point_insert(self.the_world[0][0][0], self.the_world[0][0][1], self.point_num)
            self.main_tree_refresh(0,0,self.point_num)
            self.point_num += 1
        else:
            m,n=self.child_to_root(self.draw_father[self.choose_index][0], self.draw_father[self.choose_index][1])
            a = self.the_world[m][n][0]
            b=self.the_world[m][n][1]
            c = self.the_world[self.draw_father[self.choose_index][0]][self.draw_father[self.choose_index][1]][0]
            d = self.the_world[self.draw_father[self.choose_index][0]][self.draw_father[self.choose_index][1]][1]
            if self.draw_father[self.choose_index][2]==0:
                self.left_insert(a,b,c,d)
            else:
                self.right_insert(a,b,c,d)
            x=self.the_world[self.draw_father[self.choose_index][0]][self.draw_father[self.choose_index][1]][0]
            y=self.the_world[self.draw_father[self.choose_index][0]][self.draw_father[self.choose_index][1]][1]
            self.point_insert(x,y, self.point_num)
            self.main_tree_refresh(self.draw_father[self.choose_index][0], self.draw_father[self.choose_index][1], self.point_num)
            self.point_num += 1
        self.refresh_times()#更新步骤
        self.insert_choose_refresh()#更新插入
    def main_tree_refresh(self,a,b,element):#后端更新
        self.main_tree[a][b]=element
    def insert_choose_refresh(self):#更新插入的选择listbox
        self.window2.select_node_listbox.delete(0,END)
        self.draw_father=[]
        for i in range(len(self.main_tree)-1):
            for j in range(len(self.main_tree[i])):
                if self.main_tree[i][j] != 0:
                    self.draw_child =[]
                    m,n=self.root_to_left(i,j)
                    if self.main_tree[m][n]==0:
                        self.draw_child=[m,n,0]
                        self.draw_father.append(self.draw_child)
                        text_message='第'+str(self.main_tree[i][j])+'个节点的左子树'
                        self.window2.select_node_listbox.insert(END,text_message)
                    m, n = self.root_to_right(i, j)
                    if self.main_tree[m][n]==0:
                        self.draw_child=[m,n,1]
                        self.draw_father.append(self.draw_child)
                        text_message = '第' + str(self.main_tree[i][j]) + '个节点的右子树'
                        self.window2.select_node_listbox.insert(END, text_message)
    def root_to_left(self,a,b):#计算根节点向左子树的索引
        return a+1,b*2
    def root_to_right(self,a,b):#计算根节点向右子树的索引
        return a + 1, b * 2+1
    def child_to_root(self,a,b):#计算子树向根节点的索引
        return a-1,int(b/2)
    def build_tree(self):#构建一个二叉树的表单模型
        self.main_tree=[]
        for i in range(5):
            little_tree=[]
            for j in range(2**i):
                little_tree.append(0)
            self.main_tree.append(little_tree)
    def point_insert(self,point_x,point_y,point_value):#在指定节点位置插入节点
        self.tree_canvas.create_oval(point_x-20,point_y-20,point_x+20,point_y+20,fill='#B6E7F8',outline='lightgray')
        self.window.showtree_btn = tk.Button(self.tree_canvas,text=str(point_value),relief='flat',fg='#000000',bg='#B6E7F8',font=("Helvetic",10,"bold"),command=lambda:self.read(point_value)).place(x=point_x-14, y=point_y-14,width=28, height=28)
    def left_insert(self,point1_x,point1_y,point2_x,point2_y):#插入左节点的前端展示
        self.tree_canvas.create_line(point1_x,point1_y, point2_x,point2_y, width=5, fill='red', capstyle=BUTT, arrow=LAST,arrowshape=(30, 30, 10))
    def right_insert(self,point1_x,point1_y,point2_x,point2_y):#插入右节点的前端展示
        self.tree_canvas.create_line(point1_x,point1_y, point2_x,point2_y, width=5, fill='blue', capstyle=BUTT, arrow=LAST,arrowshape=(30, 30, 10))
    def read(self,s):#读取选中的节点信息
        for i in range(len(self.main_tree)):
            for j in range(len(self.main_tree[i])):
                if self.main_tree[i][j]==s:
                    if i==0:
                        root_point = '该节点没有根节点'
                    else:
                        root_point='该节点的根节点是：节点['
                        m,n=self.child_to_root(i,j)
                        root_point +=str(self.main_tree[m][n])+']'
                    if i==4:
                        left_point='该节点没有左子树'
                        right_point = '该节点没有右子树'
                    else:
                        m,n=self.root_to_left(i,j)
                        if self.main_tree[m][n]==0:
                            left_point = '该节点没有左子树'
                        else:
                            left_point ='该节点的左子树的根节点是：节点['
                            left_point +=str(self.main_tree[m][n])+']'
                        m, n = self.root_to_right(i, j)
                        if self.main_tree[m][n] == 0:
                            right_point = '该节点没有右子树'
                        else:
                            right_point = '该节点的右子树的根节点是：节点['
                            right_point += str(self.main_tree[m][n]) + ']'
                    finaltext='该节点的编号为'+str(s)+'\n'+root_point+'\n'+left_point+'\n'+right_point
                    messagebox.showinfo('节点信息',finaltext)
                    break
            else:
                continue
            break
if __name__ == '__main__':#主函数
    root = tk.Tk()
    root.resizable(False, False)
    basedesk(root)
    root.mainloop()